package com.wk.data.tree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 寻找相同子树
 * dfs
 * @author wukai
 * @date 2023/5/5 15:01
 */
public class SameSubTree {
    public static void main(String[] args) {
        TreeNode head = new TreeNode(1);
        TreeNode node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(3);
        head.left = node1;
        head.right = node2;
        TreeNode node3 = new TreeNode(4);
        TreeNode node4 = new TreeNode(2);
        TreeNode node5 = new TreeNode(4);
        node1.left = node3;
        node2.left = node4;
        node2.right = node5;
        TreeNode node6 = new TreeNode(4);
        node4.left = node6;
        List<TreeNode> list = findSameSubTree(head);
        System.out.println(list);
    }
    public static List<TreeNode> findSameSubTree(TreeNode head){
        Map<String,Integer> map = new HashMap<>();
        List<TreeNode> ans = new ArrayList<>();
        collect(map,ans,head);
        return ans;
    }

    private static String collect(Map<String, Integer> map, List<TreeNode> ans, TreeNode treeNode) {
        if(treeNode == null)
            return "#";
        String s = treeNode.value+","+collect(map,ans,treeNode.left)+","+collect(map,ans,treeNode.right);
        map.put(s,map.getOrDefault(s,0)+1);
        if(map.get(s) == 2){
            ans.add(treeNode);
        }
        return s;
    }
}
